package MaximumWordLengthProduct;



/*        给你一个字符串数组 words ，找出并返回 length(words[i])
        * length(words[j]) 的最大值，并且这两个单词不含有公共字母。
        如果不存在这样的两个单词，返回 0 。*/
public class Solution {


 /*   这个问题的解题思路是通过位运算和位掩码来找到不含公共字母的两个单词的最大长度乘积。
            1. 创建一个数组 `bitMasks`，用于存储每个单词的位掩码。位掩码是一个整数，
            其中每个位表示字符是否出现过。对于小写字母英文字母，可以使用 26 位的二进制数
            来表示每个字符的出现情况。
            2. 遍历输入的单词数组，对于每个单词，初始化对应的位掩码为 0，
            并遍历单词中的每个字符。对于每个字符，使用位运算将其映射到位掩码中，
            例如 'a' 对应位 0，'b' 对应位 1，以此类推。
            3. 使用两重循环遍历所有单词对，对于每一对单词，
            检查它们的位掩码是否没有公共的位，即位与操作结果为 0。如果是这样，
            表示这两个单词没有公共字母。
            4. 如果找到没有公共字母的两个单词，计算它们的长度乘积，并更新最大长度乘积。
            5. 最后返回最大长度乘积。
    这个算法的关键在于将字符映射到位上，以便进行位运算，
    从而判断两个单词是否有公共字母。这个算法的时间复杂度为 O(n^2 * m)，
    其中 n 是单词数组的长度，m 是单词的平均长度。这是一种有效的解决方案，
    能够找到不含公共字母的两个单词的最大长度乘积。*/
    public int maxProduct(String[] words) {
        int n = words.length;
        int[] bitMasks = new int[n]; // 用于存储每个单词的位掩码
        int maxProduct = 0;

        // 构建每个单词的位掩码
        for (int i = 0; i < n; i++) {
            bitMasks[i] = 0;
            for (char ch : words[i].toCharArray()) {
                // 使用位运算将字符映射到位上，'a' 对应位 0，'b' 对应位 1，以此类推
                bitMasks[i] |= 1 << (ch - 'a');
            }
        }

        // 检查两个单词是否没有公共字母，并计算它们的长度乘积
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 如果两个单词的位运算结果为 0，表示它们没有公共字母
                if ((bitMasks[i] & bitMasks[j]) == 0) {
                    int product = words[i].length() * words[j].length();
                    maxProduct = Math.max(maxProduct, product);
                }
            }
        }

        return maxProduct;
    }
}
